IB1. Review of Static Compaction
A vector is a set of inputs to a system. A test set is a set of vectors that identify faults in the system. Target faults are the faults that are identified by a given set. Since cost of testing is directly proportional to the number of test vectors in the test set, short test sequences are desirable. Reduction in test set size can be achieved using static or dynamic test set compaction algorithms.
Dynamic techniques perform compaction concurrently with the test generation process. See I. Pomeranz and S. M. Reddy, "Dynamic Test Compaction for Synchronous Sequential Circuits using Static Compaction Techniques," Proc. Fault-Tolerant Computing Symp., pp. 53-61, June 1996; S. T. Chakradhar and A. Raghunathan, "Bottleneck removal algorithm for dynamic compaction in sequential circuits," IEEE Trans. on Computer-Aided Design, (Accepted for publication) 1997; E. M. Rudnick and Janak H. Patel, "Simulation-based techniques for dynamic test sequence compaction," Proc. Int. Conf. Computer-Aided Design, pp. 67-73, Nov. 1996; and T. J. Lambert and K. K. Saluja, "Methods for Dynamic Test Vector Compaction in Sequential Test Generation," Proc. Int. Conf. on VLSI Design, pp. 166-169, Jan. 1996. Dynamic techniques often require modification of the test generator.
Static compaction techniques, on the other hand, are employed after the test generation process. Hence they are independent of the test generation algorithm and do not require modifications to the test generator. In addition, static compaction techniques can further reduce the size of test sets obtained after dynamic compaction.
Several static compaction approaches for sequential circuits have been proposed in the following references: T. M. Niermann, R. K. Roy, I. H. Patel, and J. A. Abraham, "Test compaction for sequential circuits," IEEE Trans. Computer-Aided Design, vol. 11, no. 2, pp. 260-267, Feb. 1992; B. So, "Time-efficient automatic test pattern generation system," Ph.D. Thesis, EE Dept., Univ. of Wisconsin at Madison, 1994; I. Pomeranz and S. M. Reddy, "On static compaction of test sequences for synchronous sequential circuits," Proc. Design Automation Conf., pp. 215-220, June 1996; M. S. Hsiao, E. M. Rudnick, and J. H. Patel, "Fast algorithms for static compaction of sequential circuit test vectors," Proc. IEEE VLSI Test Symp., pp. 188-195, Apr. 1995.
But, some of these approaches cannot reduce test sets produced by random or simulation-based test generators. See T. M. Niermann, R. K. Roy, I. H. Patel, and J. A. Abraham, "Test compaction for sequential circuits," IEEE Trans. Computer-Aided Design, vol. 11, no. 2, pp. 260-267, Feb. 1992; B. So, "Time-efficient automatic test pattern generation system," Ph.D. Thesis, EE Dept., Univ. of Wisconsin at Madison, 1994. Static compaction techniques based on vector insertion, omission, and selection have been investigated in I. Pomeranz and S. M. Reddy, "On static compaction of test sequences for synchronous sequential circuits," Proc. Design Automation Conf., pp. 215-220, June 1996.
These techniques require multiple fault simulation passes. If a vector is omitted or swapped, the fault simulator is invoked to make sure that fault coverage is not affected. Though these techniques produce very good compaction, they are too computationally intensive to be practical.
Vector restoration techniques aim at restoring sufficient vectors necessary to detect all faults, starting with harder faults. See R. Guo, I. Pomeranz, and S. M. Reddy, "Procedures for static compaction of test sequences for synchronous sequential circuits based on vector restoration," Technical Report 8-3-1997, Electrical and Computer Engineering Department, University of Iowa, 1997. Fast static test set compaction based on removing recurring subsequences that start and end on the same states has also been reported recently in M. S. Hsiao, E. M. Rudnick, and J. H. Patel, "Fast algorithms for static compaction of sequential circuit test vectors," Proc. IEEE VLSI Test Symp., pp. 188-195, Apr. 1995. However, these test sets are not as compact as those achieved by algorithms that use multiple fault simulation passes.
Recently, compaction based on vector reordering has also been proposed. See S. T. Chakradhar and M. S. Hsiao, "Partitioning and Reordering Techniques for Static Test Sequence Compaction of Sequential Circuits," Technical Report 1997, Computers & Communications Research Lab, NEC USA Inc.
Among the known static compaction methods, compaction techniques based on vector restoration have yielded the largest compaction. See I. Pomeranz and S. M. Reddy, "Vector Restoration Based Static Compaction of Test Sequences for Synchronous Sequential Circuits," Proceedings Int. Conf. on Computer Design, pp. 360-365, University of Iowa, Aug. 1997; R. Guo, I. Pomeranz, and S. M. Reddy, "Procedures for static compaction of test sequences for synchronous sequential circuits based on vector restoration," Technical Report 8-3-1997, Electrical and Computer Engineering Department, University of Iowa, 1997.
IB2. Review of Vector Restoration Based Compaction
The test set V is an ordered sequence of vectors v.sub.1, . . . , v.sub.n. The test set detects faults f.sub.1, . . . , f.sub.z that form the fault set F. The goal of compaction algorithms is to reduce the test set without compromising on the detectability of all faults in F. If a fault is detected at vector v.sub.i of the test set, then the detection time D(f) of the fault is i. This information can be easily obtained by a pre-processing phase that involves fault simulation (with fault dropping) of test set T.
For example, the test set in FIG. 1 has 20 vectors v.sub.1, . . . , v.sub.20. This test set detects five faults f.sub.1, . . . , f.sub.5. Fault f.sub.5 is detected at vector v.sub.20. Therefore, D(f.sub.5)=20. Detection times for other faults are as shown in the figure.
Static compaction methods based on vector restoration is based on the following framework. Given a test set, fault set, and detection time for every fault, static compaction methods produce a shorter test set that detects at least as many faults as the original test set. A set of faults is chosen initially as the target faults. These faults can have the same or different detection times. If the latest detection time of any fault in the target list is t, then the restoration process finds a subsequence v.sub.i, . . . , v.sub.t (1.ltoreq.i.ltoreq.t) (1) detects all faults in the target fault list, and (2) if the subsequence is pre-pended to the restored subsequence for earlier target faults, then all earlier target faults are also detected. The next set of target faults is chosen from the faults that remain undetected by the restored vector set. This process is continued until there are no more target faults.
The techniques that rely on fault simulation to satisfy step 2 described above, are computationally intensive and impractical on large industrial designs. Among the known vector based compaction methods, the restoration omitting synchronizing prefix (RSP) is the only method which does not involve simulation to satisfy step 2. See I. Pomeranz, and S. M. Reddy, "Vector Restoration Based Static Compaction of Test Sequences for Synchronous Sequential circuits," Proceedings Int. Conf. on Computer Design, pp. 360-365, University of Iowa, Aug. 1997.
In the RSP approach, sufficient vectors are restored such that the target fault is detected starting from all unknown initial states. Consequently, independent of further additions to the restored vector sets, faults once chosen for restoration remain detected throughout the remainder of the compaction process.
A linear vector restoration method determines the subsequence by first considering only vector v.sub.t. If all target faults are not detected, then the subsequence v.sub.t-1, v.sub.t is proposed. If this sequence also does not detect all target faults, then additional vectors v.sub.t-2, . . . , v.sub.1 (in that order) are considered until all target faults are detected. More details about the complexity of this technique will be provided below.
Among the known vector restoration based compaction methods, the RSP approach requires fewer CPU seconds. Unfortunately, even the RSP approach is too slow to be practical on large industrial designs (See Table 2 in FIG. 7).
The conventional static compaction techniques including the RSP technique have at least a major problem that limit their practical usage. They require prohibitively large run-times when used for testing of large industrial designs.